Link to this headingKey Rotation

  • Update keys whenever there is a change or message

INIT Keys:

  • Handled by the Delivery Service
  • This contains data to a Public Key where we can use to encrypt data to them

Link to this headingTreeKEM

  • Uses left balancing Binary Tree of Asymmetric Public Keys
  • All of the Group Members are leafs.
  • All of the Children of the tree know the Private keys of corresponding Asymmetric Public Keys.
    • In the Example Below User C Has the private keys for H, J, and K
Key K ├── Key J │ ├── Key G │ │ ├── Key A (User A) │ │ └── Key B (User B) │ └── Key H │ ├── Key C (User C) │ └── Key D (User D) └── Key I ├── Key E (User E) └── Key F (User F)

Link to this headingINIT Operation

  1. We initialize the tree with all of the members for the group.
  2. When a member is Online they initiate a update.
    • For Example if A is Online then They update G,J,K

Link to this headingADD Operation

  1. Add a User to the tree
    • The Second member that joins makes a single root with two leaves. Example {“G”: [A,B]}
    • The Third member that joins is added to the right. Example {“K”: {“J”: [A,B], I}}
  2. Then the new user does an update
    • The I user updates the K key and sends it encrypted with the J key.

Link to this headingUpdate Operation

  1. User F Updates his key
  2. This then is hashed and sent to the I node
  3. Since the I node is updated this is then sent to the K node
  4. Now to update this to the rest of the group you send a message to the J Group and the User E
    • This uses 2 operations instead of 5

Link to this headingRemove Operation

  1. User D is removed
  2. All notes that D has the private key for are removed.
    • This means H, J, K
  3. Any User does an update to generate the tree

Why?

  • Sending a Message
    • Old Way: Encrypting 1kb message to 100K users takes 100Mb and 100K operations
    • New Way: Encrypting 1kb message to 100K users takes 1kb and 1 operation. (Uses Root Key)
  • Updating Keys
    • Old Way: Making a new key to 100K users takes 100K operations
    • New Way: Making a new key to 100K users takes 17 operations. (Updates Sub keys)
  • Removing a new User
    • Old Way: All User regenerate all keys. Takes O(N)
    • New Way: User updates tree with sub keys.
  • Adding a new User
    • Old Way: New user needs to make 100K keys for 100K users
    • New Way: New user needs to make 17 keys for 100K users